// Maciej Chałapuk (maciej@chalapuk.pl)
// vim: ts=2 sw=2 expandtab

#ifndef BITCOUNT_HPP
#define BITCOUNT_HPP

#include <cinttypes>
#include <type_traits>
#include <limits>
#include <cstdlib>


namespace experiment {

namespace bitcount {


class parallel {
public:
  template <class number>
  size_t operator() (number arg) const {
    return static_cast<size_t>(counter<sizeof(number)*8, 0>::run(arg));
  }

private:
  template <size_t size, size_t i>
  struct counter {
    template <class number>
    static number run(number arg) {
      return counter<size/2, i+1>::run(count(arg, i));
    }
    template <class number>
    static number count(number x, size_t c) {
      return (x & mask(c)) + ((x >> two(c)) & mask(c));
    }
    static size_t mask(size_t c) {
      return (static_cast<size_t>(-1) / (two(two(c)) + 1u));
    }
    static size_t two(size_t c) {
      return (static_cast<size_t>(1) << c);
    }
  };
  template <size_t i>
  struct counter<1, i> {
    template <class number>
    static number run(number arg) {
      return arg;
    }
  };
};


} // namespace bitcount

} // namespace experiment

#endif // include guard

